package com.leetcode.algorithm.y22.m08.w4;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 658. 找到 K 个最接近的元素
 * 
 * https://leetcode.cn/problems/find-k-closest-elements/
 * 
 * @author jie.deng
 *
 */
class Question0658Solution01 {

	public List<Integer> findClosestElements(int[] arr, int k, int x) {
		int len = arr.length;
		if (k >= len) {
			return IntStream.of(arr).boxed().collect(Collectors.toList());
		}
		if (arr[0] >= x) {
			return IntStream.of(arr).boxed().limit(k).collect(Collectors.toList());
		} else if (arr[len - 1] <= x) {
			return IntStream.of(arr).boxed().skip(len - k).collect(Collectors.toList());
		}

		int idx = searchLastLessIdx(arr, x);
		int left = Math.max(0, idx - k);
		int right = Math.min(len - 1, idx + k);
		while (right - left + 1 > k) {
			if (x - arr[left] > arr[right] - x) {
				left++;
			} else {
				right--;
			}
		}
		return IntStream.of(arr).boxed().skip(left).limit(k).collect(Collectors.toList());
	}

	private int searchLastLessIdx(int[] arr, int target) {
		int left = 0;
		int right = arr.length;
		// [left, right)
		while (left < right) {
			int mid = left + ((right - left + 1) >> 1);
			if (arr[mid] == target) {
				return mid;
			} else if (arr[mid] < target) {
				left = mid;
			} else {
				right = mid - 1;
			}
		}
		return left;
	}

}